Status DeleteBST(BiTree *T, int key)
{
    if( !*T )						//如果结点为空，返回错误
    {
        return FALSE;
    }
    else							//结点非空
    {
        if( key == (*T)->data )		//结点的值为key
        {
            return Delete(T);		//删除该结点
        }
        else if( key < (*T)->data )	//递归访问左子树，进行删除操作
        {
            return DeleteBST(&(*T)->lchild, key);
        }
        else						//递归访问右子树，进行删除操作
        {
            return DeleteBST(&(*T)->rchild, key);
        }
    }
}

Status Delete(BiTree *p)
{										
    BiTree q, s;					//q保存待删除的结点的指针，s保存要释放的结点（q有双侧子树）
    
    if( (*p)->rchild == NULL )		
    {
        q = *p;						//q保存待删除的结点的树指针
        *p = (*p)->lchild;			//待删除的结点的指针指向结点的左子树
        free(q);					//释放待删除的结点
    }
    else if( (*p)->lchild == NULL )
    {
        q = *p;						//q保存待删除的结点的树指针
        *p = (*p)->rchild;			//待删除的结点的指针指向结点的右子树
        free(q);					//释放待删除的结点
    }
    else							//直接前驱替换，直接前驱的左子树接上
    {
        q = *p;						//q保存待删除的结点的树指针
        s = (*p)->lchild;			//s进入待删除结点的左子树
        
        while( s->rchild )			//s不断进入右子树直到找到前驱结点
        {
            q = s;					//q每次指向s的上一层
            s = s->rchild;			
        }
        
        (*p)->data = s->data;		//换掉待删除结点的数据
        
        if( q != *p )				
        {
            q->rchild = s->lchild;	//s的左子树接到q的右子树
        }
        else					//待删除结点的左子树没有右子树，q=*p
        {
            q->lchild = s->lchild;	//s的左子树接到p的左子树
        }
        
        free(s);	//释放中介结点
    }
    
    return TRUE;
}